import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean ret = solution.isMatch("aa", "a");
        System.out.println(ret);
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        boolean dp[][] = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for(int i = 0; i <= s.length(); i++){
            for(int j = 1; j <= p.length(); j++){   // dp[i][0] = false
                char pattern = p.charAt(j - 1);
                if(pattern != '*'){
                    if (matches(s, i - 1, p, j - 1)){
                        dp[i][j] = dp[i - 1][j - 1];
                    };
                    continue;
                }
                if(matches(s, i - 1, p, j - 2)){
                    dp[i][j] = dp[i - 1][j - 2] || dp[i - 1][j];
                }
                dp[i][j] = dp[i][j] || dp[i][j - 2];
            }
        }
        return dp[s.length()][p.length()];
    }

    boolean matches(String s, int i, String p, int j){
        if(i < 0) return false;
        if(p.charAt(j) == '.' || s.charAt(i) == p.charAt(j)){
            return true;
        }
        return false;
    }
}


class Solution1 {
    public boolean isMatch(String s, String p) {

        boolean dp[][] = new boolean[s.length()][p.length()];
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            for(int j = 0; j < p.length(); j++){
                char pattern = p.charAt(j);
                char prevPattern = '#';
                if(j > 0) prevPattern = p.charAt(j - 1);

                // 四种情况满足任意一个，dp[i][j]为True
                if(pattern != '*'){
                    if (_isMatch(c, pattern)){
                        dp[i][j] = get(dp, i - 1, j - 1, p);
                    }
                }
                else{
                    if(_isMatch(c, prevPattern)){
                        dp[i][j] = get(dp, i - 1, j - 1, p)    // *匹配当前字符，*前面字符匹配前一个字符
                                || get(dp, i - 1, j, p);           // *匹配当前字符和前一个字符
                    }
                    dp[i][j] = dp[i][j]
                            || get(dp, i, j - 1, p)              // *匹配空
                            || get(dp, i, j - 2, p);             // ?*匹配空
                }
            }
        }
        return dp[s.length() - 1][p.length() - 1];
    }

    boolean _isMatch(char c, char pattern) {
        return c == pattern || pattern == '.';
    }

    boolean get(boolean dp[][], int i, int j, String p){
        if (i < 0 && j < 0) return true;
        if (i < 0 || j < 0) {
            if(j < 0) return false;
            else{
                while(j > 0 && p.charAt(j) == '*') j -= 2;
                if (j < 0) return true;
                return false;
            }
        }
        return dp[i][j];
    }
}